#include <vector>
#include <string>

using namespace std;

// 213. 打家劫舍 II
class Solution1
{
private:
    int rob(const vector<int>& nums, int begin, int end)
    {
        if(begin == end) return nums[begin];

        int n = nums.size();
        vector<int> f(n), g(n);
        f[begin] = nums[begin];
        for(int i = begin + 1; i <= end; ++i)
        {
            f[i] = max(f[i - 1], g[i - 1] + nums[i]);
            g[i] = max(f[i - 1], g[i - 1]);
        }
        return max(g[end], f[end]);
    }

public:
    int rob(vector<int>& nums) 
    {
        int n = nums.size();
        if(n == 1) return nums[0];

        int rob1 = rob(nums, 1, n - 1);
        int rob2 = rob(nums, 0, n - 2);
        return max(rob1, rob2);
    }
};

// 740. 删除并获得点数
class Solution 
{
public:
    int deleteAndEarn(vector<int>& nums) 
    {
        const int N = 1e4 + 1;
        int hash[N]{};
        for(int x : nums) hash[x] += x;

        vector<int> f(N), g(N);
        for(int i = 1; i < N; ++i)
        {
            f[i] = g[i - 1] + hash[i];
            g[i] = max(g[i - 1], f[i - 1]);
        }
        return max(f[N - 1], g[N - 1]);
    }
};

// 120. 三角形最小路径和
class Solution3
{
public:
    int minimumTotal(vector<vector<int>>& triangle) 
    {
        int n = triangle.size();
        for(int i = 1; i < n; ++i)
        {
            triangle[i][0] += triangle[i - 1][0];
            triangle[i][i] += triangle[i - 1][i - 1]; 
        }

        for(int i = 1; i < n; ++i)
        {
            for(int j = 1; j < i; ++j)
            {
                triangle[i][j] += min(triangle[i - 1][j], triangle[i - 1][j - 1]);
            }
        }

        int ret = INT_MAX;
        for(int j = 0; j < n; ++j)
        {
            ret = min(ret, triangle[n - 1][j]);
        }
        return ret; 
    }
};

// 611. 有效三角形的个数
class Solution4
{
public:
    int triangleNumber(vector<int>& nums) 
    {
        sort(nums.begin(), nums.end());
        int ret = 0, n = nums.size();
        for(int i = n - 1; i >= 2; --i)
        {
            int left = 0, right = i - 1;
            while(left < right)
            {
                if(nums[left] + nums[right] > nums[i])
                {
                    ret += right - left;
                    --right;
                }
                else
                    ++left;
            }
        }
        return ret;
    }
};

// 18. 四数之和
class Solution5
{
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) 
    {
        vector<vector<int>> ret;
        sort(nums.begin(), nums.end());
        int n = nums.size();
        for(int i = 0; i < n;)
        {
            for(int j = i + 1; j < n;)
            {
                int left = j + 1, right = n - 1;
                long long aim = (long long)target - nums[i] - nums[j];
                while(left < right)
                {
                    int sum = nums[left] + nums[right];
                    if(sum > aim) --right;
                    else if(sum < aim) ++left;
                    else
                    {
                        ret.push_back({nums[i], nums[j], nums[left++], nums[right--]});
                        while(left < right && nums[left] == nums[left - 1]) ++left;
                        while(left < right && nums[right] == nums[right + 1]) --right;
                    }
                }
                ++j;
                while(j < n && nums[j] == nums[j - 1]) ++j;
            }
            ++i;
            while(i < n && nums[i] == nums[i - 1]) ++i;
        }
        return ret;
    }
};